from random import randint
from copy import deepcopy

from utils.util import Utils
from utils.profile import Profile
from utils.bit_op import BitOp
from utils.generator import Generator
from utils.raw_obj import RawObject as Obj


# 2024/05/23 联合利剑-2024A围岛演习,主要是要注意鬼子和大漂亮的动向,估计收复蛙蛙指日可待
#            另外收复蛙蛙一定是关联的动作,反霸,清算日本鬼子,琉球复国,实现中华民族伟大复兴
# 2024/05/24 东部战区发布联合打击3D虚实动画,切以为只表决心不会下场,80后还没动,大漂亮还没动呢
#            切记:螳螂捕蝉黄雀在后,最后下场才能利益最大化
#            让反霸阵营坚定信心,不要因为伊朗莱西之死被吓到,目前为止沙特80后小萨勒曼表现不错

# ref: https://www.bilibili.com/video/BV1fy41187Z3/?spm_id_from=333.1365.list.card_archive.click&vd_source=ad559e41b561d48861f70d0187e51e02
# 我国的养老金来源:
#   1. 现收现付
#   2. 政府的财政补贴
#   3. 国企分红 (这个在私有化盛行的资本主义国家不可能实现)

class Heap(Utils):
    # 用arr[0]代表heap中的数据量,为了所有的算左右childs和parent时都用位运算
    # arr长度动态可变,切以为不适合做算法,增加数组长度会增加系统调用的时间
    def __init__(self, max_heap: bool = None):
        # max_heap 只能对 Obj 对象起作用
        super(Heap, self).__init__([0])
        self.max_heap = max_heap

    @Profile()
    def insert(self, val):
        if isinstance(val, Obj) and (self.max_heap is not None):
            val.asc = self.max_heap
        if len(self.arr) == self.arr[0] + 1:
            self.arr.append(val)
        else:
            self.arr[self.arr[0] + 1] = val
        self.arr[0] += 1
        self.heap_insert(self.arr[0])

    @Profile()
    def heap_insert(self, i):
        # 从i往上调整,直到符合堆的特性
        parent = BitOp.parent(i)
        if self.arr[i] > self.arr[parent]:
            self.swap(i, parent)
            self.heap_insert(parent)

    @Profile()
    def remove(self, i):
        if i + 1 > self.arr[0]:
            self.simple_error('index exceed')
        self.swap(i + 1, self.arr[0])
        self.arr[0] -= 1
        self.heapify(i + 1)
        return self.arr[self.arr[0] + 1]

    @Profile()
    def heapify(self, i):
        # 从i往下调整,直到符合堆的特性
        left, right = BitOp.childs(i)
        if left > self.arr[0]:
            return
        elif right > self.arr[0]:
            if self.arr[i] < self.arr[left]:
                self.swap(i, left)
                self.heapify(left)
        else:
            max_i = left if self.arr[left] >= self.arr[right] else right
            if self.arr[i] < self.arr[max_i]:
                self.swap(i, max_i)
                self.heapify(max_i)

    def get_arr(self):
        return self.arr[1:1 + self.arr[0]]

    def top(self):
        if self.arr[0]:
            return self.arr[1]

    def __len__(self):
        return self.arr[0]


class HeapSort(Heap):
    def __init__(self, arr):
        self.arr = [0] + arr

    def sort(self):
        for i in range(1, len(self.arr)):
            self.insert(self.arr[i])
        while self.arr[0] > 0:
            self.remove(0)

    def sort2(self):
        # ref: https://www.bilibili.com/video/BV1fu4y1q77y/?spm_id_from=333.999.0.0&vd_source=ad559e41b561d48861f70d0187e51e02
        # 1:14:49 改进堆建立的时间复杂度为O(N),从自上往下改为自下往上,后一半的数据并不需要调整
        # 缺点: 必须提前拿到所有数据,如果是每次得到单个的值,那么只能用insert方法
        self.arr[0] = len(self.arr) - 1
        # 此句是最大的亮点,针对没有孩子的节点,没必要调heapify方法(视频里面没讲)
        idx = BitOp.parent(self.arr[0])
        for i in range(idx):
            self.heapify(idx - i)

        while self.arr[0] > 0:
            self.remove(0)


if __name__ == '__main__':
    g = Generator(asc=False)
    h = Heap()
    for i in range(randint(10, 30)):
        r = g.single_val()
        h.insert(r)
        print(h.get_arr(), r)

    while len(h) > 0:
        x = h.remove(0)
        print(x, end=" ")
    print('')
    Profile().print_and_reset()

    arr = Generator().do()
    arr2 = deepcopy(arr)
    arr3 = deepcopy(arr)
    arr2.sort()
    print(arr)
    hs = HeapSort(arr)
    hs.sort()
    print(hs.get_arr())
    print(arr2)
    print(hs.get_arr() == arr2)

    hs2 = HeapSort(arr3)
    hs2.sort2()
    print(hs2.get_arr())
    print(hs2.get_arr() == arr2)
